public class Leetcode {
}

//leetcode:123:买股票的最佳时机III
class Solution1 {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int INT = -0x3f3f3f3f;

        //设立三个状态0：0次交易，1：1次交易，2：2次交易
        //f数组代表此时这个位置是买入股票
        int[][] f = new int[n][3];
        //g位置代表此时这个位置是卖出股票
        int[][] g = new int[n][3];

        for(int i = 0; i < 3; i++){
            f[0][i] = g[0][i] = INT;
        }
        f[0][0] = -prices[0];
        g[0][0] = 0;

        for(int i = 1; i < n; i++){
            for(int j = 0; j < 3; j++){
                f[i][j] = Math.max(f[i-1][j] , g[i-1][j] - prices[i]);
                //先进行对g的赋值
                g[i][j] = g[i-1][j];
                //由于第0个位置的值是无法进行卖出股票的，所以我们要进行判断
                if(j-1 >= 0) g[i][j] = Math.max(g[i][j] , f[i-1][j-1] + prices[i]);
            }
        }

        //然后判断卖出状态，这三次交易的最大值
        int ret = 0;
        for(int j = 0; j < 3; j++){
            ret = Math.max(ret , g[n-1][j]);
        }
        return ret;
    }
}

//leetcode:188:买股票的最佳时机IV
class Solution2 {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        int INT = -0x3f3f3f3f;
        k = Math.min(k , n / 2);

        int[][] f = new int[n][k+1];
        int[][] g = new int[n][k+1];

        for(int i = 0; i <= k; i++){
            f[0][i] = g[0][i] = INT;
        }

        f[0][0] = -prices[0];
        g[0][0] = 0;

        for(int i = 1; i < n; i++){
            for(int j = 0; j <= k; j++){
                f[i][j] = Math.max(f[i-1][j] , g[i-1][j] - prices[i]);
                g[i][j] = g[i-1][j];
                if(j-1 >= 0) g[i][j] = Math.max(g[i][j] , f[i-1][j-1] + prices[i]);
            }
        }

        int ret = 0;
        for(int j = 0; j <= k; j++){
            ret = Math.max(ret , g[n-1][j]);
        }
        return ret;
    }
}